%{
#include <stdio.h>

#include "parsetree.h"

#define YYSTYPE ParseTree *

extern char yytext[];
extern int column;

/* prototypes */
int yylex();
void yyerror(char *s);
%}
/*
 * Derived from the C parser maintained by Jutta Degener at
 *   http://www.quut.com/c/ANSI-C-grammar-y.html
 */
%token IDENTIFIER CONSTANT STRING_LITERAL SIZEOF
%token PTR_OP INC_OP DEC_OP LEFT_OP RIGHT_OP LE_OP GE_OP EQ_OP NE_OP
%token AND_OP OR_OP MUL_ASSIGN DIV_ASSIGN MOD_ASSIGN ADD_ASSIGN
%token SUB_ASSIGN LEFT_ASSIGN RIGHT_ASSIGN AND_ASSIGN
%token XOR_ASSIGN OR_ASSIGN TYPE_NAME

%token TYPEDEF EXTERN STATIC AUTO REGISTER RESTRICT INLINE
%token CHAR SHORT INT LONG SIGNED UNSIGNED FLOAT DOUBLE CONST VOLATILE VOID
%token BOOL IMAGINARY COMPLEX
%token STRUCT UNION ENUM ELLIPSIS

%token CASE DEFAULT IF ELSE SWITCH WHILE DO FOR GOTO CONTINUE BREAK RETURN

%expect 1

%start program
%%

primary_expression
        : IDENTIFIER
        | CONSTANT
        | STRING_LITERAL
        | '(' expression ')'                                                    { $$ = $2; }
        ;

postfix_expression
        : primary_expression
        | postfix_expression '[' expression ']'                                 { $$ = new ParseTree(PTTArray, $1, $3); }
        | postfix_expression '(' ')'                                            { $$ = new ParseTree(PTTFuncCall, $1, NULL); }
        | postfix_expression '(' argument_expression_list ')'                   { $$ = new ParseTree(PTTFuncCall, $1, $3); }
        | postfix_expression '.' IDENTIFIER                                     { $$ = new ParseTree(PTTElement, $1, $3); }
        | postfix_expression PTR_OP IDENTIFIER                                  { $$ = new ParseTree(PTTArrow, $1, $3); }
        | postfix_expression INC_OP                                             { $$ = new ParseTree(PTTPostInc, $1); }
        | postfix_expression DEC_OP                                             { $$ = new ParseTree(PTTPostDec, $1); }
        | '(' type_name ')' '{' initialiser_list '}'                            { $$ = new ParseTree(PTTInitialiser, $2, $5); }
        | '(' type_name ')' '{' initialiser_list ',' '}'                        { $$ = new ParseTree(PTTInitialiser, $2, $5); }
        ;

argument_expression_list
        : assignment_expression
        | argument_expression_list ',' assignment_expression                    { $$ = new ParseTree(PTTSequence, $1, $3); }
        ;

unary_expression
        : postfix_expression
        | INC_OP unary_expression                                               { $$ = new ParseTree(PTTPreInc, $2); }
        | DEC_OP unary_expression                                               { $$ = new ParseTree(PTTPreDec, $2); }
        | '&' cast_expression                                                   { $$ = new ParseTree(PTTAddressOf, $2); }
        | '*' cast_expression                                                   { $$ = new ParseTree(PTTDereference, $2); }
        | '+' cast_expression                                                   { $$ = new ParseTree(PTTUnaryPlus, $2); }
        | '-' cast_expression                                                   { $$ = new ParseTree(PTTNegate, $2); }
        | '~' cast_expression                                                   { $$ = new ParseTree(PTTBitwiseNot, $2); }
        | '!' cast_expression                                                   { $$ = new ParseTree(PTTNot, $2); }
        | SIZEOF unary_expression                                               { $$ = new ParseTree(PTTSizeof, $2); }
        | SIZEOF '(' type_name ')'                                              { $$ = new ParseTree(PTTSizeof, $3); }
        ;

cast_expression
        : unary_expression
        | '(' type_name ')' cast_expression                                     { $$ = new ParseTree(PTTCast, $2, $4); }
        ;

multiplicative_expression
        : cast_expression
        | multiplicative_expression '*' cast_expression                         { $$ = new ParseTree(PTTMultiply, $1, $3); }
        | multiplicative_expression '/' cast_expression                         { $$ = new ParseTree(PTTDivide, $1, $3); }
        | multiplicative_expression '%' cast_expression                         { $$ = new ParseTree(PTTModulus, $1, $3); }
        ;

additive_expression
        : multiplicative_expression
        | additive_expression '+' multiplicative_expression                     { $$ = new ParseTree(PTTAdd, $1, $3); }
        | additive_expression '-' multiplicative_expression                     { $$ = new ParseTree(PTTSubtract, $1, $3); }
        ;

shift_expression
        : additive_expression
        | shift_expression LEFT_OP additive_expression                          { $$ = new ParseTree(PTTShiftLeft, $1, $3); }
        | shift_expression RIGHT_OP additive_expression                         { $$ = new ParseTree(PTTShiftRight, $1, $3); }
        ;

relational_expression
        : shift_expression
        | relational_expression '<' shift_expression                            { $$ = new ParseTree(PTTLessThan, $1, $3); }
        | relational_expression '>' shift_expression                            { $$ = new ParseTree(PTTGreaterThan, $1, $3); }
        | relational_expression LE_OP shift_expression                          { $$ = new ParseTree(PTTLessThanOrEqual, $1, $3); }
        | relational_expression GE_OP shift_expression                          { $$ = new ParseTree(PTTGreaterThanOrEqual, $1, $3); }
        ;

equality_expression
        : relational_expression
        | equality_expression EQ_OP relational_expression                       { $$ = new ParseTree(PTTEqual, $1, $3); }
        | equality_expression NE_OP relational_expression                       { $$ = new ParseTree(PTTNotEqual, $1, $3); }
        ;

and_expression
        : equality_expression
        | and_expression '&' equality_expression                                { $$ = new ParseTree(PTTBitwiseAnd, $1, $3); }
        ;

exclusive_or_expression
        : and_expression
        | exclusive_or_expression '^' and_expression                            { $$ = new ParseTree(PTTBitwiseXor, $1, $3); }
        ;

inclusive_or_expression
        : exclusive_or_expression
        | inclusive_or_expression '|' exclusive_or_expression                   { $$ = new ParseTree(PTTBitwiseOr, $1, $3); }
        ;

logical_and_expression
        : inclusive_or_expression
        | logical_and_expression AND_OP inclusive_or_expression                 { $$ = new ParseTree(PTTLogicalAnd, $1, $3); }
        ;

logical_or_expression
        : logical_and_expression
        | logical_or_expression OR_OP logical_and_expression                    { $$ = new ParseTree(PTTLogicalOr, $1, $3); }
        ;

conditional_expression
        : logical_or_expression
        | logical_or_expression '?' expression ':' conditional_expression       { $$ = new ParseTree(PTTTernaryOp, $1, $3, $5); }
        ;

assignment_expression
        : conditional_expression
        | unary_expression '=' assignment_expression                            { $$ = new ParseTree(PTTAssign, $1, $3); }
        | unary_expression MUL_ASSIGN assignment_expression                     { $$ = new ParseTree(PTTMultiplyAssign, $1, $3); }
        | unary_expression DIV_ASSIGN assignment_expression                     { $$ = new ParseTree(PTTDivideAssign, $1, $3); }
        | unary_expression MOD_ASSIGN assignment_expression                     { $$ = new ParseTree(PTTModulusAssign, $1, $3); }
        | unary_expression ADD_ASSIGN assignment_expression                     { $$ = new ParseTree(PTTAddAssign, $1, $3); }
        | unary_expression SUB_ASSIGN assignment_expression                     { $$ = new ParseTree(PTTSubtractAssign, $1, $3); }
        | unary_expression LEFT_ASSIGN assignment_expression                    { $$ = new ParseTree(PTTShiftLeftAssign, $1, $3); }
        | unary_expression RIGHT_ASSIGN assignment_expression                   { $$ = new ParseTree(PTTShiftRightAssign, $1, $3); }
        | unary_expression AND_ASSIGN assignment_expression                     { $$ = new ParseTree(PTTBitwiseAndAssign, $1, $3); }
        | unary_expression XOR_ASSIGN assignment_expression                     { $$ = new ParseTree(PTTBitwiseXorAssign, $1, $3); }
        | unary_expression OR_ASSIGN assignment_expression                      { $$ = new ParseTree(PTTBitwiseOrAssign, $1, $3); }
        ;

expression
        : assignment_expression
        | expression ',' assignment_expression                                  { $$ = new ParseTree(PTTSequence, $1, $3); }
        ;

constant_expression
        : conditional_expression
        ;

declaration
        : declaration_specifiers ';'
        | declaration_specifiers init_declarator_list ';'                       { $$ = new ParseTree(PTTSequence, $1, $2); }
        ;

declaration_specifiers
        : storage_class_specifier
        | storage_class_specifier declaration_specifiers                        { $$ = new ParseTree(PTTSequence, $1, $2); }
        | type_specifier
        | type_specifier declaration_specifiers                                 { $$ = new ParseTree(PTTSequence, $1, $2); }
        | type_qualifier
        | type_qualifier declaration_specifiers                                 { $$ = new ParseTree(PTTSequence, $1, $2); }
        | INLINE                                                                { $$ = new ParseTree(PTTTypeInline); }
        | INLINE declaration_specifiers                                         { $$ = new ParseTree(PTTTypeInline, $2); }
        ;

init_declarator_list
        : init_declarator
        | init_declarator_list ',' init_declarator                              { $$ = new ParseTree(PTTSequence, $1, $3); }
        ;

init_declarator
        : declarator
        | declarator '=' initialiser                                            { $$ = new ParseTree(PTTAssign, $1, $3); }
        ;

storage_class_specifier
        : TYPEDEF                                                               { $$ = new ParseTree(PTTTypeTypedef); }
        | EXTERN                                                                { $$ = new ParseTree(PTTTypeExtern); }
        | STATIC                                                                { $$ = new ParseTree(PTTTypeStatic); }
        | AUTO                                                                  { $$ = new ParseTree(PTTTypeAuto); }
        | REGISTER                                                              { $$ = new ParseTree(PTTTypeRegister); }
        ;

type_specifier
        : VOID                                                                  { $$ = new ParseTree(PTTTypeVoid); }
        | CHAR                                                                  { $$ = new ParseTree(PTTTypeChar); }
        | SHORT                                                                 { $$ = new ParseTree(PTTTypeShort); }
        | INT                                                                   { $$ = new ParseTree(PTTTypeInt); }
        | LONG                                                                  { $$ = new ParseTree(PTTTypeLong); }
        | FLOAT                                                                 { $$ = new ParseTree(PTTTypeFloat); }
        | DOUBLE                                                                { $$ = new ParseTree(PTTTypeDouble); }
        | SIGNED                                                                { $$ = new ParseTree(PTTTypeSigned); }
        | UNSIGNED                                                              { $$ = new ParseTree(PTTTypeUnsigned); }
        | BOOL                                                                  { $$ = new ParseTree(PTTTypeBool); }
        | COMPLEX                                                               { $$ = new ParseTree(PTTTypeComplex); }
        | IMAGINARY                                                             { $$ = new ParseTree(PTTTypeImaginary); }
        | struct_or_union_specifier
        | enum_specifier
        | TYPE_NAME
        ;

struct_or_union_specifier
        : STRUCT IDENTIFIER '{' struct_declaration_list '}'                     { $$ = new ParseTree(PTTTypeStruct, $2, $4); }
        | STRUCT '{' struct_declaration_list '}'                                { $$ = new ParseTree(PTTTypeStruct, NULL, $4); }
        | STRUCT IDENTIFIER                                                     { $$ = new ParseTree(PTTTypeStruct, $2); }
        | UNION IDENTIFIER '{' struct_declaration_list '}'                      { $$ = new ParseTree(PTTTypeUnion, $2, $4); }
        | UNION '{' struct_declaration_list '}'                                 { $$ = new ParseTree(PTTTypeUnion, NULL, $4); }
        | UNION IDENTIFIER                                                      { $$ = new ParseTree(PTTTypeUnion, $2); }
        ;

struct_declaration_list
        : struct_declaration
        | struct_declaration_list struct_declaration                            { $$ = new ParseTree(PTTSequence, $1, $2); }
        ;

struct_declaration
        : specifier_qualifier_list struct_declarator_list ';'                   { $$ = new ParseTree(PTTStructDeclaration, $1, $2); }
        ;

specifier_qualifier_list
        : type_specifier specifier_qualifier_list                               { $$ = new ParseTree(PTTSpecifierQualifierList, $1, $2); }
        | type_specifier
        | type_qualifier specifier_qualifier_list                               { $$ = new ParseTree(PTTSpecifierQualifierList, $1, $2); }
        | type_qualifier
        ;

struct_declarator_list
        : struct_declarator
        | struct_declarator_list ',' struct_declarator                          { $$ = new ParseTree(PTTSequence, $1, $2); }
        ;

struct_declarator
        : declarator                                                            { $$ = new ParseTree(PTTStructDeclarator, $1, NULL); }
        | ':' constant_expression                                               { $$ = new ParseTree(PTTStructDeclarator, NULL, $2); }
        | declarator ':' constant_expression                                    { $$ = new ParseTree(PTTStructDeclarator, $1, $3); }
        ;

enum_specifier
        : ENUM '{' enumerator_list '}'                                          { $$ = new ParseTree(PTTEnumSpecifier, NULL, $3); }
        | ENUM IDENTIFIER '{' enumerator_list '}'                               { $$ = new ParseTree(PTTEnumSpecifier, $2, $4); }
        | ENUM '{' enumerator_list ',' '}'                                      { $$ = new ParseTree(PTTEnumSpecifier, NULL, $3); }
        | ENUM IDENTIFIER '{' enumerator_list ',' '}'                           { $$ = new ParseTree(PTTEnumSpecifier, $2, $4); }
        | ENUM IDENTIFIER                                                       { $$ = new ParseTree(PTTEnumSpecifier, $2); }
        ;

enumerator_list
        : enumerator
        | enumerator_list ',' enumerator                                        { $$ = new ParseTree(PTTSequence, $1, $3); }
        ;

enumerator
        : IDENTIFIER
        | IDENTIFIER '=' constant_expression                                    { $$ = new ParseTree(PTTAssign, $1, $3); }
        ;

declarator
        : pointer direct_declarator                                             { $$ = new ParseTree(PTTTypePointer, $1, $2); }
        | direct_declarator
        ;


direct_declarator
        : IDENTIFIER
        | '(' declarator ')'
        | direct_declarator '[' type_qualifier_list assignment_expression ']'   { $$ = new ParseTree(PTTTypeArrayDeclarator, $1, $3, $4); }
        | direct_declarator '[' type_qualifier_list ']'                         { $$ = new ParseTree(PTTTypeArrayDeclarator, $1, $3, NULL); }
        | direct_declarator '[' assignment_expression ']'                       { $$ = new ParseTree(PTTTypeArrayDeclarator, $1, NULL, $3); }
        | direct_declarator '[' STATIC type_qualifier_list assignment_expression ']' { $$ = new ParseTree(PTTTypeArrayDeclarator, $1, $4, $5); }
        | direct_declarator '[' type_qualifier_list STATIC assignment_expression ']' { $$ = new ParseTree(PTTTypeArrayDeclarator, $1, $3, $5); }
        | direct_declarator '[' type_qualifier_list '*' ']'
        | direct_declarator '[' '*' ']'
        | direct_declarator '[' ']'                                             { $$ = new ParseTree(PTTTypeArrayDeclarator, $1); }
        | direct_declarator '(' parameter_type_list ')'                         { $$ = new ParseTree(PTTTypeFunction, $1, $3); }
        | direct_declarator '(' identifier_list ')'                             { $$ = new ParseTree(PTTTypeFunction, $1, $3); }
        | direct_declarator '(' ')'                                             { $$ = new ParseTree(PTTTypeFunction, $1); }
        ;

pointer
        : '*'                                                                   { $$ = new ParseTree(PTTPointer); }
        | '*' type_qualifier_list                                               { $$ = new ParseTree(PTTPointer, $2); }
        | '*' pointer                                                           { $$ = new ParseTree(PTTPointer, NULL, $2); }
        | '*' type_qualifier_list pointer                                       { $$ = new ParseTree(PTTPointer, $2, $3); }
        ;

type_qualifier
        : CONST
        | RESTRICT
        | VOLATILE
        ;

type_qualifier_list
        : type_qualifier
        | type_qualifier_list type_qualifier                                    { $$ = new ParseTree(PTTSequence, $1, $2); }
        ;


parameter_type_list
        : parameter_list
        | parameter_list ',' ELLIPSIS                                           { $$ = new ParseTree(PTTSequence, $1, new ParseTree(PTTEllipsis)); }
        ;

parameter_list
        : parameter_declaration
        | parameter_list ',' parameter_declaration                              { $$ = new ParseTree(PTTSequence, $1, $3); }
        ;

parameter_declaration
        : declaration_specifiers declarator
        | declaration_specifiers abstract_declarator
        | declaration_specifiers
        ;

identifier_list
        : IDENTIFIER
        | identifier_list ',' IDENTIFIER
        ;

type_name
        : specifier_qualifier_list
        | specifier_qualifier_list abstract_declarator
        ;

abstract_declarator
        : pointer
        | direct_abstract_declarator
        | pointer direct_abstract_declarator
        ;

direct_abstract_declarator
        : '(' abstract_declarator ')'
        | '[' ']'
        | '[' assignment_expression ']'
        | direct_abstract_declarator '[' ']'
        | direct_abstract_declarator '[' assignment_expression ']'
        | '[' '*' ']'
        | direct_abstract_declarator '[' '*' ']'
        | '(' ')'
        | '(' parameter_type_list ')'
        | direct_abstract_declarator '(' ')'
        | direct_abstract_declarator '(' parameter_type_list ')'
        ;

initialiser
        : assignment_expression
        | '{' initialiser_list '}'
        | '{' initialiser_list ',' '}'
        ;

initialiser_list
        : initialiser
        | designation initialiser
        | initialiser_list ',' initialiser
        | initialiser_list ',' designation initialiser
        ;

designation
        : designator_list '='
        ;

designator_list
        : designator
        | designator_list designator                                            { $$ = new ParseTree(PTTSequence, $1, $2); }
        ;

designator
        : '[' constant_expression ']'                                           { $$ = new ParseTree(PTTDesignatorIndex, $1); }
        | '.' IDENTIFIER                                                        { $$ = new ParseTree(PTTDesignatorMember, $1); }
        ;

statement
        : labeled_statement
        | compound_statement
        | expression_statement
        | selection_statement
        | iteration_statement
        | jump_statement
        ;

labeled_statement
        : IDENTIFIER ':' statement                                              { $$ = new ParseTree(PTTLabel, $1, $3); }
        | CASE constant_expression ':' statement                                { $$ = new ParseTree(PTTCase, $1, $3); }
        | DEFAULT ':' statement                                                 { $$ = new ParseTree(PTTCase, NULL, $3); }
        ;

compound_statement
        : '{' '}'                                                               { $$ = new ParseTree(PTTNoop); }
        | '{' block_item_list '}'                                               { $$ = new ParseTree(PTTBlock, $2); }
        ;

block_item_list
        : block_item
        | block_item_list block_item                                            { $$ = new ParseTree(PTTSequence, $1, $2); }
        ;

block_item
        : declaration
        | statement
        | error ';'
        ;

expression_statement
        : ';'                                                                   { $$ = new ParseTreeValue(new Value()); }
        | expression ';'                                                        { $$ = $1; }
        ;

selection_statement
        : IF '(' expression ')' statement                                       { $$ = new ParseTree(PTTIf, $3, $5); }
        | IF '(' expression ')' statement ELSE statement                        { $$ = new ParseTree(PTTIf, $3, $5, $7); }
        | SWITCH '(' expression ')' statement                                   { $$ = new ParseTree(PTTSwitch, $3, $5); }
        ;

iteration_statement
        : WHILE '(' expression ')' statement                                    { $$ = new ParseTree(PTTWhile, $3, $5); }
        | DO statement WHILE '(' expression ')' ';'                             { $$ = new ParseTree(PTTDoWhile, $2, $5); }
        | FOR '(' expression_statement expression_statement ')' statement       { $$ = new ParseTree(PTTFor, NULL, $3, $4, $6); }
        | FOR '(' expression_statement expression_statement expression ')' statement { $$ = new ParseTree(PTTFor, $3, $4, $5, $7); }
        | FOR '(' declaration expression_statement ')' statement                { $$ = new ParseTree(PTTFor, $3, $4, NULL, $6); }
        | FOR '(' declaration expression_statement expression ')' statement     { $$ = new ParseTree(PTTFor, $3, $4, $5, $7); }
        ;

jump_statement
        : GOTO IDENTIFIER ';'                                                   { $$ = new ParseTree(PTTGoto, $2); }
        | CONTINUE ';'                                                          { $$ = new ParseTree(PTTContinue); }
        | BREAK ';'                                                             { $$ = new ParseTree(PTTBreak); }
        | RETURN ';'                                                            { $$ = new ParseTree(PTTReturn); }
        | RETURN expression ';'                                                 { $$ = new ParseTree(PTTReturn, $2); }
        ;

program
        : translation_unit                                                      { ProgramTree = $$; }
        ;

translation_unit
        : external_declaration
        | translation_unit external_declaration                                 { $$ = new ParseTree(PTTSequence, $1, $2); }
        ;

external_declaration
        : function_definition
        | declaration
        ;

function_definition
        : declaration_specifiers declarator declaration_list compound_statement { $$ = new ParseTree(PTTFuncDef, $1, $2, $3, $4); }
        | declaration_specifiers declarator compound_statement                  { $$ = new ParseTree(PTTFuncDef, $1, $2, NULL, $3); }
        ;

declaration_list
        : declaration
        | declaration_list declaration
        ;


%%
void yyerror(char *s)
{
        fflush(stdout);
        printf("\n%*s\n%*s\n", column, "^", column, s);
}
